import java.util.Arrays;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2023-11-12
 * Time:16:05
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9,4,1,2,0,6,5,3,10,7,8};
        mergeSort(arr,0,arr.length-1,new int[arr.length]);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right,int[] tmp) {
        if(left < right) {
            //分
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,tmp);
            mergeSort(arr,mid + 1,right,tmp);

            //治--合
            sort(arr,left,mid,right,tmp);
        }
    }
    private static void sort(int[] arr, int left,int mid, int right,int[] tmp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if(arr[i] < arr[j]) {
                tmp[t++] = arr[i++];
            } else {
                tmp[t++] = arr[j++];
            }
        }
        while (i <= mid) {
            tmp[t++] = arr[i++];
        }
        while (j <= right) {
            tmp[t++] = arr[j++];
        }
        t = 0;
        for(int k = left;k <= right;k++) {
            arr[k] = tmp[t++];
        }
    }
}